/*
 * Copyright (c) 2023 fred
 * Licensed under the Apache License,Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */
import { Token} from './Token';
import { ParseSettings } from './ParseSettings';
import { Node } from '../nodes/Node';
import { TreeBuilder } from './TreeBuilder';
import List from '@ohos.util.List';
import { Element } from '../nodes/Element';
// import { FormElement } from '../nodes/FormElement';
import { Reader } from '../io/Reader';
import { Parser } from './Parser';
import { StringReader } from '../io/StringReader';
import { HtmlTreeBuilderState, HtmlTreeBuilderStateConstants, HtmlTreeBuilderStates } from './HtmlTreeBuilderState';
import { TokeniserStates } from './TokeniserState';
import { Document } from '../nodes/Document';
import { ParseError } from './ParseError';
import { Comment } from '../nodes/Comment';
import { CDataNode } from '../nodes/CDataNode';
import { DataNode } from '../nodes/DataNode';
import { TextNode } from '../nodes/TextNode';
import { StringUtil } from '../internal/StringUtil';
import { Validate } from '../helper/Validate';
import { TokenEndTag } from './token/TokenEndTag';
import { TokenCharacter } from './token/TokenCharacter';
import { TokenStartTag } from './token/TokenStartTag';
import { TokenComment } from './token/TokenComment';
import hilog from '@ohos.hilog';
import logUtil from '../util/LogUtil';
import { FormElement } from '../nodes/FormElement';

export class HtmlTreeBuilder extends TreeBuilder {

  // tag searches. must be sorted, used in inSorted. MUST update HtmlTreeBuilderTest if more arrays are added.
  static readonly TagsSearchInScope: string[] = ["applet", "caption", "html", "marquee", "object", "table", "td", "th"]
  static readonly TagSearchList: string[] = ["ol", "ul"]
  static readonly TagSearchButton: string[] = ["button"]
  static readonly TagSearchTableScope: string[] = ["html", "table"]
  static readonly TagSearchSelectScope: string[] = ["optgroup", "option"]
  static readonly TagSearchEndTags: string[] = ["dd", "dt", "li", "optgroup", "option", "p", "rp", "rt"]
  static readonly TagThoroughSearchEndTags = ["caption", "colgroup", "dd", "dt", "li", "optgroup", "option", "p", "rb", "rp", "rt", "rtc", "tbody", "td", "tfoot", "th", "thead", "tr"]
  static readonly TagSearchSpecial: string[] = ["address", "applet", "area", "article", "aside", "base", "basefont", "bgsound",
    "blockquote", "body", "br", "button", "caption", "center", "col", "colgroup", "command", "dd",
    "details", "dir", "div", "dl", "dt", "embed", "fieldset", "figcaption", "figure", "footer", "form",
    "frame", "frameset", "h1", "h2", "h3", "h4", "h5", "h6", "head", "header", "hgroup", "hr", "html",
    "iframe", "img", "input", "isindex", "li", "link", "listing", "marquee", "menu", "meta", "nav",
    "noembed", "noframes", "noscript", "object", "ol", "p", "param", "plaintext", "pre", "script",
    "section", "select", "style", "summary", "table", "tbody", "td", "textarea", "tfoot", "th", "thead",
    "title", "tr", "ul", "wbr", "xmp"]

  // prevents the parser bogging down in exceptionally broken pages
  public static readonly MaxScopeSearchDepth = 100;

  // the current state
  private _state: HtmlTreeBuilderState;
  // original / marked state
  private _originalState: HtmlTreeBuilderState;

  private _baseUriSetFromDoc: boolean;
  // the current head element
  private _headElement: Element;
  // the current form element
  private _formElement: FormElement;
  // fragment parse context -- could be null even if fragment parsing
  private _contextElement: Element;
  // active (open) formatting elements
  private _formattingElements: List<Element>;
  // stack of Template Insertion modes
  private _tmplInsertMode: List<HtmlTreeBuilderState>
  // chars in table to be shifted out
  private _pendingTableCharacters: List<TokenCharacter>;
  // reused empty end tag
  private _emptyEnd: TokenEndTag;

  // if ok to go into frameset
  private _framesetOk: boolean;
  // if next inserts should be fostered
  private _fosterInserts: boolean;
  // if parsing a fragment of html
  private _fragmentParsing: boolean;

  defaultSettings(): ParseSettings {
    return ParseSettings.htmlDefault
  }

  newInstance(): TreeBuilder {
    return new HtmlTreeBuilder()
  }

  initialiseParse(input: Reader, baseUri: string, parser: Parser) {
    super.initialiseParse(input, baseUri, parser)
    // this is a bit mucky. todo - probably just create new parser objects to ensure all reset.
    this._state = HtmlTreeBuilderStates.Initial
    this._originalState = null
    this._baseUriSetFromDoc = false
    this._headElement = null
    this._formElement = null
    this._contextElement = null
    this._formattingElements = new List()
    this._tmplInsertMode = new List()
    this._pendingTableCharacters = new List()
    this._emptyEnd = new TokenEndTag()
    this._framesetOk = true
    this._fosterInserts = false
    this._fragmentParsing = false
  }

  parseFragment(inputFragment: string, context: Element, baseUri: string, parser: Parser): List<Node> {
    // context may be null
    this._state = HtmlTreeBuilderStates.Initial
    this.initialiseParse(new StringReader(inputFragment), baseUri, parser)
    this._contextElement = context
    this._fragmentParsing = true
    let root: Element = null
    if (context !== undefined && context !== null) {
      if (context.ownerDocument() !== null) {
        this.doc.setQuirksMode(context.ownerDocument().getQuirksMode())
      }
      // initialise the tokeniser state:
      let contextTag = context.normalName()
      switch (contextTag) {
        case "title":
        case "textarea":
          this.tokeniser.transition(TokeniserStates.Rcdata)
          break
        case "iframe":
        case "noembed":
        case "noframes":
        case "style":
        case "xml":
          this.tokeniser.transition(TokeniserStates.Rawtext)
          break
        case "script":
          this.tokeniser.transition(TokeniserStates.ScriptData)
          break
        case "noscript":
        // if scripting enabled, rawtext
          this.tokeniser.transition(TokeniserStates.Data)
          break
        case "plaintext":
          this.tokeniser.transition(TokeniserStates.PLAINTEXT)
          break;
        case "template":
          this.tokeniser.transition(TokeniserStates.Data)
          this.pushTemplateMode(HtmlTreeBuilderStates.InTemplate)
          break
        default:
          this.tokeniser.transition(TokeniserStates.Data)
      }
      root = new Element(this.tagFor(contextTag, this.settings), baseUri)
      this.doc.appendChild(root)
      this.stack.add(root)
      this.resetInsertionMode()
      // setup form element to nearest form on context (up ancestor chain). ensures form controls are associated
      // with form correctly
      let formSearch = context
      while (formSearch !== undefined && formSearch !== null) {
        if (formSearch instanceof FormElement) {
          this._formElement = formSearch
          break
        }
        formSearch = formSearch.parent()
      }
    }

    this.runParser()
    if (context !== undefined && context !== null) {
      // depending on context and the input html, content may have been added outside of the root el
      // e.g. context=p, input=div, the div will have been pushed out.
      let nodes = root.siblingNodes()
      if (nodes.length > 0) {
        root.insertChildren(-1, nodes)
      }
      return root.childNodes()
    } else {
      return this.doc.childNodes()
    }
  }


  process(token: Token, state: HtmlTreeBuilderState | null = null): boolean {
    this.currentToken = token
    if (state === undefined || state === null) {
      logUtil.i("fredzz",`process:${this._state.name()} `)
      return this._state.process(token, this)
    } else {
      return state.process(token, this)
    }
  }


  transition(state: HtmlTreeBuilderState) {
    this._state = state
  }

  state(): HtmlTreeBuilderState {
    return this._state
  }

  markInsertionMode() {
    this._originalState = this._state;
  }

  originalState(): HtmlTreeBuilderState {
    return this._originalState
  }

  setFramesetOk(framesetOk: boolean) {
    this._framesetOk = framesetOk
  }

  getFramesetOk(): boolean {
    return this._framesetOk
  }

  getDocument(): Document {
    return this.doc
  }

  getBaseUri(): string {
    return this.baseUri
  }

  maybeSetBaseUri(base: Element) {
    // only listen to the first <base href> in parse
    if (this._baseUriSetFromDoc) {
      return
    }
    let href = base.absUrl("href")
    if (href !== undefined && href.length > 0) {
      // ignore <base target> etc
      this.baseUri = href
      this._baseUriSetFromDoc = true
      // set on the doc so doc.createElement(Tag) will get updated base, and to update all descendants
      this.doc.setBaseUri(href)
    }
  }

  isFragmentParsing(): boolean {
    return this._fragmentParsing
  }

  errorState(state: HtmlTreeBuilderState) {
    if (this.parser.getErrors().canAddError()) {
      this.parser.getErrors().add(new ParseError(this.reader, `"Unexpected ${this.currentToken.tokenType()} token [${this.currentToken}] when in state [${state}]`))
    }
  }

  insert(startTag: TokenStartTag| null): Element {
    if (startTag === undefined || startTag === null) {
      return
    }
    this.dedupeAttributes(startTag)
    // handle empty unknown tags
    // when the spec expects an empty tag, will directly hit insertEmpty, so won't generate this fake end tag.
    if (startTag.isSelfClosing()) {
      let el = this.insertEmpty(startTag)
      this.stack.add(el)
      // handles <script />, otherwise needs breakout steps from script data
      this.tokeniser.transition(TokeniserStates.Data)
      this.tokeniser.emit(this._emptyEnd.reset().setName(el.getTagName()))
      return el
    }
    let el = new Element(this.tagFor(startTag.getName(), this.settings), null, this.settings.normalizeAttributes(startTag.attributes))
    this.insertElement(el, startTag)
    return el
  }

  insertStartTag(startTagName: string): Element {
    let el = new Element(this.tagFor(startTagName, this.settings), null)
    this.insertElement(el)
    return el
  }

  private insertElement(el: Element, token: Token | null = null) {
    this.insertNode(el, token)
    this.stack.add(el)
  }

  insertEmpty(startTag: TokenStartTag): Element {
    this.dedupeAttributes(startTag)
    let tag = this.tagFor(startTag.getName(), this.settings)
    let el = new Element(tag, null, this.settings.normalizeAttributes(startTag.attributes))
    this.insertNode(el, startTag)
    if (startTag.isSelfClosing()) {
      if (tag.isKnownTag()) {
        if (!tag.isEmpty()) {
          this.tokeniser.error(`Tag [${tag.normalName()}] cannot be self closing; not a void tag"`)
        }
      } else {
        // unknown tag, remember this is self closing for output
        tag.setSelfClosing()
      }
    }
    return el
  }

  insertForm(startTag: TokenStartTag, onStack: boolean, checkTemplateStack: boolean) {
    this.dedupeAttributes(startTag)
    let tag = this.tagFor(startTag.getName(), this.settings)
    let el = new FormElement(tag, null, this.settings.normalizeAttributes(startTag.attributes))
    if (checkTemplateStack) {
      if (!this.onStack("template")) {
        this.setFormElement(el)
      }
    } else {
      this.setFormElement(el)
    }
    this.insertNode(el, startTag)
    if (onStack) {
      this.stack.add(el)
    }
    return el
  }

  insertComment(commentToken: TokenComment | null) {
    if (commentToken === undefined || commentToken === null) {
      return
    }
    let comment = new Comment(commentToken.getData())
    this.insertNode(comment, commentToken)
  }

  insertCharacter(characterToken: TokenCharacter | null, el: Element | null = null) {
    if (characterToken === undefined || characterToken === null) {
      return
    }
    if (el === undefined || el === null) {
      el = this.currentElement()
    }
    let node: Node
    let tagName = el.normalName()
    let data = characterToken.getData()
    if (characterToken.isCData()) {
      node = new CDataNode(data)
    } else if (this.isContentForTagData(tagName)) {
      node = new DataNode(data)
    } else {
      node = new TextNode(data)
    }
  }

  /** Inserts the provided character token into the provided element. Use when not going onto stack element */
  private insertNode(node: Node, token: Token) {
    // if the stack hasn't been set up yet, elements (doctype, comments) go into the doc
    if (this.stack.isEmpty()) {
      this.doc.appendChild(node)
    } else if (this.isFosterInserts() && StringUtil.inSorted(this.currentElement().normalName(), HtmlTreeBuilderStateConstants.InTableFoster)) {
      this.insertInFosterParent(node)
    } else {
      this.currentElement().appendChild(node)
    }
    // connect form controls to their form element
    if (node instanceof Element && (node as Element).getTag().isFormListed()) {
      if (this._formElement !== undefined && this._formElement !== null) {
        this._formElement.addElement(node)
      }
    }
    this.onNodeInserted(node, token)
  }

  /** Cleanup duplicate attributes. **/
  private dedupeAttributes(startTag: TokenStartTag) {
    if (startTag.hasAttributes() && !startTag.attributes.isEmpty()) {
      let dupes = startTag.attributes.deduplicate(this.settings)
      if (dupes > 0) {
        this.error(`Dropped duplicate attribute(s) in tag [${startTag.normalName}]`)
      }
    }
  }

  pop(): Element {
    let size = this.stack.length
    return this.stack.removeByIndex(size - 1)
  }

  push(element: Element) {
    this.stack.add(element)
  }

  getStack(): List<Element> {
    return this.stack
  }

  onStack(el: Element | string): boolean {
    if (el instanceof Element) {
      return HtmlTreeBuilder.onStack(this.stack, el)
    } else {
      let stack = this.getFromStack(el)
      return stack !== undefined && stack !== null
    }
  }

  // an arbitrary tension point between real HTML and crafted pain
  private static readonly maxQueueDepth = 256

  private static onStack(queue: List<Element>, element: Element): boolean {
    let bottom = queue.length - 1
    let upper = bottom >= HtmlTreeBuilder.maxQueueDepth ? bottom - HtmlTreeBuilder.maxQueueDepth : 0
    for (let pos = bottom; pos >= upper; pos--) {
      let next = queue.get(pos)
      if (next === element) {
        return true
      }
    }
    return false
  }

  getFromStack(elName: string): Element | null {
    let bottom = this.stack.length - 1
    let upper = bottom >= HtmlTreeBuilder.maxQueueDepth ? bottom - HtmlTreeBuilder.maxQueueDepth : 0
    for (let pos = bottom; pos >= upper; pos--) {
      let next = this.stack.get(pos)
      if (next.normalName() === elName) {
        return next
      }
    }
    return null
  }

  removeFromStack(el: Element): boolean {
    for (let pos = this.stack.length - 1; pos >= 0; pos--) {
      let next = this.stack.get(pos)
      if (next === el) {
        this.stack.removeByIndex(pos)
        return true
      }
    }
    return false
  }

  popStackToClose(elName: string): Element {
    for (let pos = this.stack.length - 1; pos >= 0; pos--) {
      let el = this.stack.get(pos)
      this.stack.removeByIndex(pos)
      if (el.normalName() === elName) {
        if (this.currentToken instanceof TokenEndTag) {
          this.onNodeClosed(el, this.currentToken)
        }
        return el
      }
    }
    return null
  }

  popStackToCloses(...elNames: string[]) {
    for (let pos = this.stack.length - 1; pos >= 0; pos--) {
      let el = this.stack.get(pos)
      this.stack.removeByIndex(pos)
      if (StringUtil.inSorted(el.normalName(), elNames)) {
        if (this.currentToken instanceof TokenEndTag) {
          this.onNodeClosed(el, this.currentToken)
        }
        break
      }
    }
  }

  clearStackToTableContext() {
    this.clearStackToContext("table", "template")
  }

  clearStackToTableBodyContext() {
    this.clearStackToContext("tbody", "tfoot", "thead", "template")
  }

  clearStackToTableRowContext() {
    this.clearStackToContext("tr", "template")
  }

  private clearStackToContext(...nodeNames: string[]) {
    for (let pos = this.stack.length - 1; pos >= 0; pos--) {
      let next = this.stack.get(pos)
      if (StringUtil.in(next.normalName(), ...nodeNames) || next.normalName() === "html") {
        break;
      } else {
        this.stack.removeByIndex(pos);
      }
    }
  }

  aboveOnStack(el: Element): Element | null {
    if (this.onStack(el)) {
      for (let pos = this.stack.length - 1; pos >= 0; pos--) {
        let next = this.stack.get(pos)
        if (next === el) {
          return this.stack.get(pos - 1)
        }
      }
    } else {
      return null
    }
  }

  insertOnStackAfter(after: Element, inElement: Element) {
    let i = this.stack.getLastIndexOf(after)
    Validate.isTrue(i != -1)
    this.stack.insert(inElement, i + 1)
  }

  replaceOnStack(out: Element, inElement: Element) {
    this.replaceInQueue(this.stack, out, inElement)
  }

  private replaceInQueue(queue: List<Element>, out: Element, inElement: Element) {
    let i = queue.getLastIndexOf(out)
    Validate.isTrue(i != -1)
    queue.set(i, inElement)
  }

  /**
   * Reset the insertion mode, by searching up the stack for an appropriate insertion mode. The stack search depth
   * is limited to {@link #maxQueueDepth}.
   * @return true if the insertion mode was actually changed.
   */
  resetInsertionMode(): boolean {
    // https://html.spec.whatwg.org/multipage/parsing.html#the-insertion-mode
    let last = false
    let bottom = this.stack.length - 1
    let upper = bottom >= HtmlTreeBuilder.maxQueueDepth ? bottom - HtmlTreeBuilder.maxQueueDepth : 0
    let origState = this._state
    if (this.stack.length === 0) {
      // nothing left of stack, just get to body
      this.transition(HtmlTreeBuilderStates.InBody)
    }
    LOOP: for (let pos = bottom; pos >= upper; pos--) {
      let node = this.stack.get(pos)
      if (pos === upper) {
        last = true
        if (this._fragmentParsing) {
          node = this._contextElement
        }
      }
      let name = (node !== undefined && node !== null) ? node.normalName() : ""
      switch (name) {
        case "select":
          this.transition(HtmlTreeBuilderStates.InSelect);
        // todo - should loop up (with some limit) and check for table or template hits
          break LOOP;
        case "td":
        case "th":
          if (!last) {
            this.transition(HtmlTreeBuilderStates.InCell);
            break LOOP;
          }
          break;
        case "tr":
          this.transition(HtmlTreeBuilderStates.InRow);
          break LOOP;
        case "tbody":
        case "thead":
        case "tfoot":
          this.transition(HtmlTreeBuilderStates.InTableBody);
          break LOOP;
        case "caption":
          this.transition(HtmlTreeBuilderStates.InCaption);
          break LOOP;
        case "colgroup":
          this.transition(HtmlTreeBuilderStates.InColumnGroup);
          break LOOP;
        case "table":
          this.transition(HtmlTreeBuilderStates.InTable);
          break LOOP;
        case "template":
          let tmplState = this.currentTemplateMode();
          Validate.notNull(tmplState, "Bug: no template insertion mode on stack!");
          this.transition(tmplState);
          break LOOP;
        case "head":
          if (!last) {
            this.transition(HtmlTreeBuilderStates.InHead);
            break LOOP;
          }
          break;
        case "body":
          this.transition(HtmlTreeBuilderStates.InBody);
          break LOOP;
        case "frameset":
          this.transition(HtmlTreeBuilderStates.InFrameset);
          break LOOP;
        case "html":
          this.transition(this._headElement == null ? HtmlTreeBuilderStates.BeforeHead : HtmlTreeBuilderStates.AfterHead);
          break LOOP;
      }
      if (last) {
        this.transition(HtmlTreeBuilderStates.InBody)
        break
      }
    }
    return this._state !== origState
  }

  /** Places the body back onto the stack and moves to InBody, for cases in AfterBody / AfterAfterBody when more content comes */
  resetBody() {
    if (!this.onStack("body")) {
      this.stack.add(this.doc.body())
    }
    this.transition(HtmlTreeBuilderStates.InBody)
  }

  // todo: tidy up in specific scope methods
  private specificScopeTarget: string[] = [null]

  private inSpecificScope(targetName: string, baseTypes: string[], extraTypes: string[]) {
    this.specificScopeTarget[0] = targetName
    return this.inSpecificScope1(this.specificScopeTarget, baseTypes, extraTypes)
  }

  private inSpecificScope1(targetNames: string[], baseTypes: string[], extraTypes: string[]) {
    // https://html.spec.whatwg.org/multipage/parsing.html#has-an-element-in-the-specific-scope
    let bottom = this.stack.length - 1
    let upper = bottom >= HtmlTreeBuilder.maxQueueDepth ? bottom - HtmlTreeBuilder.maxQueueDepth : 0
    // don't walk too far up the tree
    for (let pos = bottom; pos >= upper; pos--) {
      let elName = this.stack.get(pos).normalName()
      if (StringUtil.inSorted(elName, targetNames)) {
        return true
      }
      if (StringUtil.inSorted(elName, baseTypes)) {
        return false
      }
      if (extraTypes !== undefined && extraTypes !== null && StringUtil.inSorted(elName, extraTypes)) {
        return false
      }
    }
    return false
  }

  inScope1(targetNames: string[]) {
    return this.inSpecificScope1(targetNames, HtmlTreeBuilder.TagsSearchInScope, null)
  }

  inScope(targetName: string, extras: string[] | null = null) {
    return this.inSpecificScope(targetName, HtmlTreeBuilder.TagsSearchInScope, extras)
    // todo: in mathml namespace: mi, mo, mn, ms, mtext annotation-xml
    // todo: in svg namespace: forignOjbect, desc, title
  }

  inListItemScope(targetName: string): boolean {
    return this.inScope(targetName, HtmlTreeBuilder.TagSearchList)
  }

  inButtonScope(targetName: string): boolean {
    return this.inScope(targetName, HtmlTreeBuilder.TagSearchButton)
  }

  inTableScope(targetName: string): boolean {
    return this.inSpecificScope(targetName, HtmlTreeBuilder.TagSearchTableScope, null)
  }

  inSelectScope(targetName: string): boolean {
    for (let pos = this.stack.length - 1; pos >= 0; pos--) {
      let el = this.stack.get(pos)
      let elName = el.normalName()
      if (elName === targetName) {
        return true
      }
      // all elements except
      if (!StringUtil.inSorted(elName, HtmlTreeBuilder.TagSearchSelectScope)) {
        return false
      }
    }
    Validate.fail("Should not be reachable")
    return false
  }

  /** Tests if there is some element on the stack that is not in the provided set. */
  onStackNot(allowedTags: string[]): boolean {
    let bottom = this.stack.length - 1
    let top = bottom > HtmlTreeBuilder.MaxScopeSearchDepth ? bottom - HtmlTreeBuilder.MaxScopeSearchDepth : 0
    // don't walk too far up the tree
    for (let pos = bottom; pos >= top; pos--) {
      let elName = this.stack.get(pos).normalName()
      if (!StringUtil.inSorted(elName, allowedTags)) {
        return true
      }
    }
    return false
  }

  setHeadElement(headElement: Element) {
    this._headElement = headElement
  }

  getHeadElement(): Element {
    return this._headElement
  }

  isFosterInserts(): boolean {
    return this._fosterInserts
  }

  setFosterInserts(fosterInserts: boolean) {
    this._fosterInserts = fosterInserts
  }

  getFormElement(): FormElement {
    return this._formElement
  }

  setFormElement(formElement: FormElement) {
    this._formElement = formElement
  }

  resetPendingTableCharacters() {
    this._pendingTableCharacters = new List()
  }

  getPendingTableCharacters(): List<TokenCharacter> {
    return this._pendingTableCharacters
  }

  addPendingTableCharacters(c: TokenCharacter) {
    // make a clone of the token to maintain its state (as Tokens are otherwise reset)
    let clone = c.clone()
    this._pendingTableCharacters.add(clone)
  }

  /**
   13.2.6.3 Closing elements that have implied end tags
   When the steps below require the UA to generate implied end tags, then, while the current node is a dd element, a dt element, an li element, an optgroup element, an option element, a p element, an rb element, an rp element, an rt element, or an rtc element, the UA must pop the current node off the stack of open elements.

   If a step requires the UA to generate implied end tags but lists an element to exclude from the process, then the UA must perform the above steps as if that element was not in the above list.

   When the steps below require the UA to generate all implied end tags thoroughly, then, while the current node is a caption element, a colgroup element, a dd element, a dt element, an li element, an optgroup element, an option element, a p element, an rb element, an rp element, an rt element, an rtc element, a tbody element, a td element, a tfoot element, a th element, a thead element, or a tr element, the UA must pop the current node off the stack of open elements.

   @param excludeTag If a step requires the UA to generate implied end tags but lists an element to exclude from the
   process, then the UA must perform the above steps as if that element was not in the above list.
   */
  generateImpliedEndTags(excludeTag: string | boolean | null = null) {
    if (excludeTag === null) {
      excludeTag = false
    }
    if (typeof excludeTag === 'string') {
      while (StringUtil.inSorted(this.currentElement().normalName(), HtmlTreeBuilder.TagSearchEndTags)) {
        if (excludeTag !== undefined && excludeTag !== null && this.currentElementIs(excludeTag)) {
          break
        }
        this.pop()
      }
    } else {
      let search = excludeTag ? HtmlTreeBuilder.TagThoroughSearchEndTags : HtmlTreeBuilder.TagSearchEndTags
      while (StringUtil.inSorted(this.currentElement().normalName(), search)) {
        this.pop()
      }
    }
  }

  closeElement(name: string) {
    this.generateImpliedEndTags(name)
    if (!(name === this.currentElement().normalName())) {
      this.errorState(this.state())
    }
    this.popStackToClose(name)
  }

  isSpecial(el: Element): boolean {
    // todo: mathml's mi, mo, mn
    // todo: svg's foreigObject, desc, title
    let name = el.normalName()
    return StringUtil.inSorted(name, HtmlTreeBuilder.TagSearchSpecial)
  }

  lastFormattingElement(): Element | null {
    return this._formattingElements.length > 0 ? this._formattingElements.get(this._formattingElements.length - 1) : null
  }

  positionOfElement(el: Element): number {
    for (let i = 0; i < this._formattingElements.length; i++) {
      if (el === this._formattingElements.get(i)) {
        return i
      }
    }
    return -1
  }

  removeLastFormattingElement(): Element | null {
    let size = this._formattingElements.length
    if (size > 0) {
      return this._formattingElements.removeByIndex(size - 1)
    } else {
      return null
    }
  }

  // active formatting elements
  pushActiveFormattingElements(inElement: Element) {
    this.checkActiveFormattingElements(inElement)
    this._formattingElements.add(inElement)
  }

  pushWithBookmark(inElement: Element, bookmark: number) {
    this.checkActiveFormattingElements(inElement)
    // catch any range errors and assume bookmark is incorrect - saves a redundant range check.
    try {
      this._formattingElements.insert(inElement, bookmark)
    } catch (e) {
      this._formattingElements.add(inElement)
    }
  }

  checkActiveFormattingElements(inElement: Element) {
    let numSeen = 0
    let size = this._formattingElements.length - 1
    let ceil = size - HtmlTreeBuilder.maxUsedFormattingElements
    if (ceil < 0) {
      ceil = 0
    }
    for (let pos = size; pos >= ceil; pos--) {
      let el = this._formattingElements.get(pos)
      if (el === undefined || el === null) {
        break
      }
      if (this.isSameFormattingElement(inElement, el)) {
        numSeen++
      }
      if (numSeen === 3) {
        this._formattingElements.removeByIndex(pos)
        break
      }
    }
  }

  private isSameFormattingElement(a: Element, b: Element): boolean {
    return a.normalName() === b.normalName() && a.attributes().equals(b.attributes())
  }

  reconstructFormattingElements() {
    if (this.stack.length > HtmlTreeBuilder.maxQueueDepth) {
      return
    }
    let last = this.lastFormattingElement()
    if (last === undefined || last === null || this.onStack(last)) {
      return
    }
    let entry = last
    let size = this._formattingElements.length
    let ceil = size - HtmlTreeBuilder.maxUsedFormattingElements
    if (ceil < 0) {
      ceil = 0
    }
    let pos = size - 1
    let skip = false
    while (true) {
      // step 4. if none before, skip to 8
      if (pos === ceil) {
        skip = true
        break
      }
      // step 5. one earlier than entry
      entry = this._formattingElements.get(--pos)
      // step 6 - neither marker nor on stack
      if (entry === undefined || entry === null || this.onStack(entry)) {
        // jump to 8, else continue back to 4
        break
      }
    }
    while (true) {
      if (!skip) {
        // step 7: on later than entry
        entry = this._formattingElements.get(++pos)
      }
      // should not occur, as we break at last element
      Validate.notNull(entry)
      // 8. create new element from element, 9 insert into current node, onto stack
      skip = false // can only skip increment from 4.
      let newEl = new Element(this.tagFor(entry.normalName(), this.settings), null, entry.attributes().clone())
      this.insertElement(newEl)
      // 10. replace entry with new entry
      this._formattingElements.set(pos, newEl)
      //11
      if (pos === size - 1) {
        // if not last entry in list, jump to 7
        break
      }
    }
  }

  // limit how many elements get recreated
  private static readonly maxUsedFormattingElements = 12;

  clearFormattingElementsToLastMarker() {
    while (!this._formattingElements.isEmpty()) {
      let el = this.removeLastFormattingElement()
      if (el === undefined || el === null) {
        break
      }
    }
  }

  removeFromActiveFormattingElements(el: Element) {
    for (let pos = this._formattingElements.length - 1; pos >= 0; pos--) {
      let next = this._formattingElements.get(pos)
      if (next === el) {
        this._formattingElements.removeByIndex(pos)
        break
      }
    }
  }

  isInActiveFormattingElements(el: Element): boolean {
    return HtmlTreeBuilder.onStack(this._formattingElements, el)
  }

  getActiveFormattingElement(nodeName: string): Element | null {
    for (let pos = this._formattingElements.length - 1; pos >= 0; pos--) {
      let next = this._formattingElements.get(pos)
      if (next === undefined || next === null) {
        break
      } else if (next.normalName() === nodeName) {
        return next
      }
    }
    return null
  }

  replaceActiveFormattingElement(out: Element, inElement: Element) {
    this.replaceInQueue(this._formattingElements, out, inElement)
  }

  insertMarkerToFormattingElements() {
    this._formattingElements.add(null)
  }

  insertInFosterParent(inNode: Node) {
    let fosterParent: Element
    let lastTable = this.getFromStack('table')
    let isLastTableParent = false
    if (lastTable !== undefined && lastTable !== null) {
      if (lastTable.parent() !== undefined && lastTable.parent() !== null) {
        fosterParent = lastTable.parent()
        isLastTableParent = true
      } else {
        fosterParent = this.aboveOnStack(lastTable)
      }
    } else {
      fosterParent = this.stack.get(0)
    }
    if (isLastTableParent) {
      // last table cannot be null by this point.
      Validate.notNull(lastTable);
      lastTable.before(inNode);
    } else {
      fosterParent.appendChild(inNode)
    }
  }

  // Template Insertion Mode stack
  pushTemplateMode(state: HtmlTreeBuilderState) {
    this._tmplInsertMode.add(state)
  }

  popTemplateMode(): HtmlTreeBuilderState | null {
    if (this._tmplInsertMode.length > 0) {
      return this._tmplInsertMode.removeByIndex(this._tmplInsertMode.length - 1)
    } else {
      return null
    }
  }

  templateModeSize(): number {
    return this._tmplInsertMode.length
  }

  currentTemplateMode(): HtmlTreeBuilderState | null {
    return this._tmplInsertMode.length > 0 ? this._tmplInsertMode.get(this._tmplInsertMode.length - 1) : null
  }

  public toString(): string {
    return `TreeBuilder{currentToken=${this.currentToken}, state=${this._state}, currentElement=${this.currentElement()}}`
  }

  isContentForTagData(normalName: string): boolean {
    return normalName === "script" || normalName === "style";
  }
}
